package Lecture9;

import java.security.acl.Permission;
import java.util.Arrays;

public class exercise {

	public static void main(String[] args)
	{

		int[] arr = {3,5,7,2,9,7,4,4,6,7,3,2,1};
		System.out.println(Arrays.toString(arr));

		arr = buildHeap(arr);
		System.out.println(Arrays.toString(arr));
		
		arr = sortHeap(arr);
		System.out.println(Arrays.toString(arr));
		
	}
	
	
	public static int[] buildHeap (int[] arr)
	{
		
		for(int i = 0; i < arr.length; i++)
		{
			int nodeIndex = i;

				while(nodeIndex != 0)
				{
					int parentIndex = (nodeIndex - 1)/2;

					if (arr[parentIndex] < arr[nodeIndex])
					{
						int temp = arr[parentIndex];
						arr[parentIndex] = arr[nodeIndex];
						arr[nodeIndex] = temp;
						

					}
					nodeIndex = parentIndex;
				}			
		}
		

		return arr;
	}
	
	
	public static  int[] sortHeap ( int[] arr)
	{

		buildHeap(arr);

		for(int i = 0; i < arr.length; i++)
		{

			int heapSize = arr.length - i - 1;
			
			swap(arr, 0, heapSize);                               // swap the first element with the last

			int parentInd = 0;									

			while(true)
			{
				int leftChildInd = parentInd*2 + 1;
				int righrChildInd = parentInd*2 + 2;
				
				if(leftChildInd >= heapSize)        //no child's
				{
					break;
				}
				else 													// there are some child's
					if ( righrChildInd >= heapSize)  			// only left
					{
						if ( arr[parentInd] < arr[leftChildInd])      // if left Child bigger than parent
						{
							swap(arr, parentInd, leftChildInd);
						}
						break;
					}
				
					else											// more then one child
					{
						
						if(arr[leftChildInd] > arr[righrChildInd])   //if left child bigger than right child...
						{
							if(arr[leftChildInd] > arr[parentInd])   // ...and if left bigger than parent...
							{
								swap(arr, leftChildInd, parentInd);  //  ...swap left and parent
								
							}
							parentInd = leftChildInd;
							
						}
						else 										//right child bigger than left...
						{
							if(arr[righrChildInd] > arr[parentInd])  //... and if right child bigger than parent
							{
								swap(arr, righrChildInd, parentInd);  // ... swap right and parent
								
							}
							
							parentInd = righrChildInd;
						}
						
						
						
						
						
					}
				
				
				
			}
			
			
		}
		
		
		
		
		
		return arr;
	}


	private static void swap(int[] arr, int i, int j) 
	{
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	

}
